Методи вирішення завдань, засновані на зведенні їх до пошуку, залежать від особливостей предметної області, в якій вирішується завдання, і від вимог, що пред'являються користувачем до рішення. Особливості предметної області:
обсяг простору, в якому доведеться шукати рішення;
ступінь змінності області у часі та просторі (статичні і динамічні області);
повнота моделі, яка описує область, якщо модель не повна, то для опису області використовують кілька моделей, які доповнюють один одного;
визначеність даних про розв'язуваної задачі, ступінь точності (помилковості) та повноти (неповноти) даних.
Вимоги користувача до результату завдання, розв'язуваної за допомогою пошуку, можна характеризувати:
кількістю рішень: одне рішення, кілька рішень, всі рішення.
властивостями результату: обмеження, яким повинен задовольняти отриманий результат і (або) способом його отримання.
Існуючі методи вирішення завдань, які використовуються в експертних системах, можна класифікувати наступним чином:
методи пошуку в одному просторі - методи, призначені для використання в наступних умовах: області невеликий розмірності, повнота моделі, точні і повні дані;
методи пошуку в ієрархічних просторах - методи, призначені для роботи в областях великої розмірності;
методи пошуку при неточних і неповних даних;
методи пошуку, використовують кілька моделей, призначені для роботи з областями, для адекватного опису яких однієї моделі недостатньо.
Передбачається, що перераховані методів при необхідності повинні об'єднуватися для того, щоб дозволити вирішувати завдання, складність яких зростає одночасно за кількома параметрами.
3.1. ПОШУК РІШЕНЬ В ОДНОМУ ПРОСТОРІ
Методи пошуку рішень в одному просторі зазвичай діляться на:
пошук у просторі станів (розглянемо докладно),
пошук методом редукції,
евристичний пошук
пошук методом "генерація-перевірка".
3.1.1. Пошук в просторі станів
Завдання пошуку в просторі станів зазвичай формулюється в теоретико-графових інтерпретації.
Нехай задана трійка (S0, F, SТ), де S0 - безліч початкових станів (умови задачі), F - множина операторів завдання, що відображають одні стану в інші, SТ - безліч кінцевих (цільових) станів (рішень задачі).
Мета: визначати таку послідовність операторів, яка перетворює початкові стану в кінцеві.
Процес рішення у вигляді графа G = (Х, Y), де X = {х0, х1 ,...} - безліч (у загальному випадку нескінченне) вершин графа, станів, а Y - множина, що містить пари вершин (xi, xj ), (xi, xj) Î X. Якщо кожна пара (xi, xj) невпорядкований, то її називають ребром, а граф - неорієнтованим. Якщо для кожної пари (xi, xj) задано порядок (напрямок), то пару (xi, xj) називають дугою (орієнтованим ребром), а граф називають орієнтованим (спрямованим). Вершини пари (xi, xj) називають кінцевими точками ребра (дуги).
Пошук в просторі станів природно представити у вигляді орієнтованого графа. Наявність пари (xi, xj) свідчить про існування деякого оператора f (fÎ F), що перетворює стан, що відповідає вершині xi, в стан xj. Для деякої вершини xi виділяємо безліч усіх спрямованих пар (xi, xj) Î Y, т.ь. множина дуг, що виходять з вершини хi, (батьківської вершини), і безліч вершин (званих дочірніми вершинами), в які ці дуги приводять. Безліч дуг, що виходять з вершини xi, відповідає множині операторів, які можуть бути застосовані до стану, що відповідає вершині хi.
У безлічі вершин X виділяють підмножина вершин Х0Í Х, відповідне безлічі початкових станів (So),, і підмножина вершин ХтÍ X, відповідне безлічі кінцевих (цільових) станів (SТ). Безліч ХТ може бути задане як явно, так і неявно, тобто через властивості, якими повинні володіти цільові стану.
Відзначимо, що граф С може бути заданий явно і неявно. Неявно завдання графа G стоїть у визначенні безлічі Х0Í Х (відповідного безлічі початкових станів) і безлічі операторів, які, будучи застосовні до деякої вершині графа, дають всі її дочірні вершини.
Отже, граф G задає простір станів, тобто простір, в якому здійснюється пошук рішення. Побудова простору здійснюється за допомогою наступного процесу. Береться якась вершина х0Í Х, до неї застосовуються всі можливі оператори, які породжують всі дочірні вершини. Цей процес називають процесом розкриття вершин. Якщо отримана цільова вершина, то вона не розкривається. Процес побудови простору станів закінчується, коли всі нерозкриті вершини є цільовими, або термінальними (тобто вершинами, до яких не можна застосувати жодних операторів). У зв'язку з тим, що простір станів може містити безліч вершин, на практиці процес породження простору обмежують або часом, або об'ємом пам'яті.
На практиці потрібно забезпечити повноту пошуку, тобто організувати пошук так, щоб всі цільові вершини були знайдені, якщо вони існують. Надійним способом забезпечення повноти є повний перебір всіх вершин. Для завдання процесу перебору необхідно визначити. порядок, в якому будуть перебиратися вершини графа. Звичайно виділяють два основних способи пошуку:
пошук в глибину (спочатку розкривається та вершина, яка була побудована самої останньої). Ріс.3.1.а
пошук в ширину. (Вершини розкриваються в тому ж порядку, в якому вони породжуються.) Ріс.3.1.б.
Цільові вершини позначені чорними квадратами, а термінальні - білими квадратами. При використанні кожного із способів можуть бути знайдені всі рішення. При переборі всього простору обидва методи будуть аналізувати однакову кількість вершин, однак метод пошуку в ширину буде вимагати істотно більше пам'яті, так як він запам'ятовує всі шляхи пошуку (а не один, як при пошуку в глибину).
3.1.2. Пошук методом редукції
При пошуку методом редукції вирішення завдання зводиться до вирішення сукупності утворюють її підзадач. Цей процес повторюється для кожної підзадачі до тих пір, поки кожна з отриманого набору підзадач, що утворюють рішення вихідної задачі, не буде мати очевидне рішення. Процес рішення задачі розбивкою її на підзадачі можна представити у вигляді спеціального спрямованого графа G, званого І / АБО-графом; Кожній вершині цього графа ставиться у відповідність опис деякої задачі (підзадачі). У графі виділяють два типи вершин: кон'юнктивні вершини і диз'юнктивні вершини.
Рішення задачі при пошуку методом редукції (при пошуку в І / АБО-графі) зводиться до знаходження в І / АБО-графі вирішального графа.
Мета процесу пошуку в І / АБО-графі - показати, що початкова вершина розв'язна, тобто для цієї вершини існує вирішальний граф. Визначення вирішуваною вершини в ТА / АБО-графі можна сформулювати рекурсивно наступним чином:
Кінцеві (цільові) вершини можна розв'язати, оскільки їх рішення відоме по вихідній припущенням.
Вершина АБО розв'язна тоді і тільки тоді, коли можна вирішити принаймні одна з її дочірніх вершин.
Вершина І вирішити толу і тільки тоді, коли можна вирішити кожна з її дочірніх вершин.
Вирішальний граф визначається як підграф з розв'язаних вершин, який показує, що початкова вершина розв'язна (згідно з наведеним вище визначенням). На рис. 3.3. розв'язні вершини затемнена, а нерозв'язні залишені білими.
Для графа І / АБО, так само як для пошуку в просторі станів, можна визначити пошук в глибину і пошук у ширину як у прямому, так і в зворотному напрямку. На рис. 3.4. наведено приклад пошуку в ширину (рис. 3.4., а) і пошуку в глибину (рис. 3.4., б). На малюнку вершини пронумеровані в тому порядку, в якому вони розкривалися, кінцеві вершини позначені квадратами, розв'язні вершини затемнена, дуги вирішального графа виділені подвійними лініями.
3.1.3. Евристичний пошук
При збільшенні простору пошуку методи сліпого пошуку вимагають надмірних витрат часу та (або) пам'яті. Це призвело до створення евристичних методів пошуку, тобто методів, що використовують деяку інформацію про предметну область для розгляду не всього простору пошуку, а таких шляхів у ньому, які з найбільшою ймовірністю приводять. до мети. '
3.1.4.Поіск методом "генерація-перевірка"
Процес пошуку може бути сформульовано в термінах "генерація-перевірка". Для здійснення процесу пошуку необхідно генерувати чергове можливе рішення (стан або підзадачі) і перевірити, чи не є воно результуючим.
3.2. ПОШУК В ІЄРАРХІЇ ПРОСТОРІВ
Методи пошуку в одному просторі не дозволяють вирішувати складні завдання, оскільки із збільшенням розміру простору час пошуку експоненціально зростає. При великому розмірі простору пошуку можна спробувати розбити загальний простір на підпростору і здійснювати пошук спочатку в них. Простір пошуку представлено ієрархією просторів.
Методи пошуку рішення в ієрархічних просторах зазвичай діляться на:
пошук в факторізованном просторі,
пошук у фіксованому безлічі просторів
пошук у мінливому безлічі просторів.
3.2.1. Пошук в факторізованном просторі
У багатьох програмах потрібно знайти всі рішення. Наприклад - постановка діагнозу. Простір називається факторізованним, якщо воно розбивається на непересічні підпростору (класи) частковими (неповними) рішеннями. Причому по виду часткового рішення можна визначити, що воно не приведе до успіху, тобто що всі повні рішення, утворені з нього, не приведуть до цільових рішень. Пошук в факторізованном просторі здійснюється на основі метолу "ієрархічна генерація-перевірка". Якщо простір пошуку вдається факторізовать, то пошук навіть у дуже великому просторі можна організувати ефективно.
3.2.2. Пошук у фіксованому безлічі просторів
Застосування методу факторизації простору обмежено тим, що для ряду областей не вдається по частковому вирішенню зробити висновок про його непридатність. Наприклад завдання планування і конструювання. У цих випадках можуть бути застосовані методи пошуку, які використовують ідею абстрактного простору. Абстракція повинна підкреслити важливі особливості розглянутої задачі, дозволити розбити задачу на більш прості підзадачі і визначити послідовність підзадач (план рішення), що приводить до вирішення основного завдання.
3.2.3. Пошук у мінливому безлічі ієрархічних просторів
У ряді програм не вдається все розв'язувані завдання звести до фіксованого набору підзадач. План виконання завдання в даному випадку повинен мати змінну структуру і не може бути зведений до фіксованого набору підзадач. Для вирішення подібних завдань може бути використаний метод спадного уточнення. Цей метод базується на наступних припущеннях:
можливо здійснити часткове впорядкування понять області, прийнятне для всіх вирішуваних завдань;
рішення, що приймаються на верхніх рівнях, немає потреби скасовувати на більш нижніх.
3.3. ПОШУК В АЛЬТЕРНАТИВНИХ ПРОСТОРАХ
Розглянуті вище методи пошуку виходять з мовчазною передумови, що знання про предметну область і дані про розв'язуваної задачі є точними і повними і для них справедливо наступне:
всі твердження, що описують стан, є справжніми;
застосування оператора до деякого станом формує деякий новий стан, опис якого складається тільки з істинних фактів.
Однак при вирішенні будь-яких практичних завдань і особливо при вирішенні неформалізованих завдань поширена зворотна ситуація. Експертові доводиться працювати в умовах неповноти і неточності знань (даних) і, як правило, в умовах дефіциту часу. Коли експерт вирішує задачу, він використовує методи, які відрізняються від формальних математичних міркувань. У цьому випадку експерт робить правдоподібні припущення, які він не може довести; тим самим питання про їх істинності залишається відкритим. Усі твердження, отримані на основі цих правдоподібних припущень, також не можуть бути доведені.
Отже, для того щоб система могла робити висновки, засновані на здоровому глузді, при роботі з неповними (неточними) даними і знаннями, вона повинна бути здатна робити припущення, а при отриманні нової інформації, яка б показала помилковість припущень, відмовлятися як від зроблених припущень, так і від умовиводів, отриманих на основі цих припущень. Думка системи про те, які факти мають місце, змінюється в ході міркування, тобто можна говорити про ревізію думок. Таким чином, навіть якщо розглядати проблемну область як статичну, неповнота (і неточність) знань і даних тягне за собою розгляд цієї області при різних (і навіть протилежних) припущеннях, що, у свою чергу, призводить до подання області у вигляді альтернативних просторів, відповідних різним, можливо, суперечливим і (або) взаємодоповнюючим припущеннями і думок.
Всі невдачі, що виникли при пошуку в одному напрямку, не запам'ятовуються при переході до пошуку в іншому напрямку. Та ж сама причина невдачі може заново виявлятися і на новому напрямку.
Здійснювати повернення доцільно не до стану, безпосередньо попереднього даному, а до того стану, який є причиною виникнення невдачі. У використовуваних нами термінах причиною невдач є припущення, тобто недоведені твердження. Тому при виявленні невдачі необхідно повертатися в стан, де це припущення було зроблено, і відчувати інше припущення.
Цей метод пошуку називають пошуком, які направляються залежністю.
3.4. ПОШУК З ВИКОРИСТАННЯМ КІЛЬКОХ МОДЕЛЕЙ
Всі методи пошуку, розглянуті до сих пір, використовували при поданні проблемної області якусь одну модель, тобто розглядали область з якоїсь однієї точки зору. При вирішенні складних завдань в умовах обмежених ресурсів використання декількох моделей може значно підвищити потужність системи. Об'єднання в одній системі декількох моделей дає можливість подолати такі труднощі.
перехід з однієї моделі на іншу дозволяє обходити тупики, що виникають під час пошуку в процесі поширення обмежень.
використання декількох моделей дозволяє в ряді випадків зменшити ймовірність втрати гарного рішення (наслідок неповного пошуку, викликаного обмеженістю ресурсів) за рахунок конструювання повного вирішення з обмеженого числа часткових кандидатів шляхом їх розширення і комбінації.
наявність декількох моделей дозволяє системі справлятися з неточністю (ошибочностью) даних.
Слід зазначити, що використання декількох моделей вимагає додаткових знань про те, як створювати і об'єднувати різні точки зору.
3.5. ВИБІР МЕТОДУ РОЗВ'ЯЗАННЯ ЗАДАЧ
Вибір методу розв'язання задачі залежить насамперед від складності завдання, що визначається особливостями проблемної області та вимог, що пред'являються користувачем до вирішення завдання. Для подолання труднощів, викликаних великим простором пошуку, використовуються методи, засновані на введенні ієрархії просторів (конкретних, абстрактних і метапространств). Найпростіший з цих методів грунтується на факторізуемості простору рішень, що дозволяє виробляти раннє відсікання. Метод забезпечує отримання всіх рішень. Якщо простір пошуку не вдається факторізовать, але при цьому не потрібно отримувати всі рішення або вибирати краще, то можуть бути застосовані методи, які використовують ієрархію однорідних абстрактних просторів. Якщо простір пошуку таке, що будь-яке завдання може бути зведена до відомої заздалегідь послідовності підзадач, то використовується фіксоване абстрактне простір.
Ефективність цього методу визначається можливістю використовувати безповоротну стратегію. У випадку, якщо підзадачі взаємозалежні, тобто для вирішення певної підзадачі може вимагатися інформація, що отримується інший підзадачі, і підзадачі не можуть бути впорядковані, доцільно застосовувати принцип найменших звершень. Цей підхід дозволяє припиняти рішення підзадачі, для якої бракує інформації, переходити до вирішення іншої підзадачі і повертатися до вихідної завданню, коли відсутня інформація стане доступною. (Пошук в ієрархії просторі)
Для подолання труднощів, викликаних неповнотою і (або) неточністю даних (знань), використовують імовірнісні, розмиті і точні методи. Всі ці методи грунтуються на ідеї збільшення надійності шляхом комбінування фактів і використання метазнаній про можливості комбінування фактів.
Для подолання неадекватності моделі проблемної області використовуються методи, орієнтовані на використання декількох моделей. Ці методи дозволяють об'єднати можливості різних моделей, що описують проблемну галузь з різних точок зору. Крім того, використання декількох моделей дозволяє зменшити ймовірність втрати гарного рішення, незважаючи на неповноту пошуку, викликану обмеженістю обчислювальних ресурсів.